package org.clockwise.multimethod;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;

import org.clockwise.driver.LinkerDriver;
import org.clockwise.srw.AccountRelationPool;
import org.clockwise.util.MyMath;

public class PageRank {

	public static double alpha = 1.0;
	public static double epsilon = 0.00001;

	/*
	 * public static double[] weight = { 2.197456684802683, 3.9157857924281956,
	 * 0.8377978156306475, 2.7185397998570457, 0.8865330506637288,
	 * 0.39180082230631763, -1.229463506332571, 1.323963658265213,
	 * -2.603764168838509, 2.5362858655562284, 1.3685754583459853,
	 * -0.6071788979793586, -0.11194352110777264, 3.402099451828893,
	 * 0.25209491973658715, -0.006432059849505724, 1.9385735317381991,
	 * 0.9999999999999665, };
	 */

	/*
	 * public static double[] weight = { 2.201658889818469, 3.833330642329824,
	 * 0.8689834415169545, 2.7272086389501355, 1.019071429171702,
	 * 0.4550984957304582, -1.586409648928933, 1.1794713266945844,
	 * -3.805691923965425, 2.754342591716569, 1.3593285684243073,
	 * -0.7550312164314843, -0.17715659686028032, 3.334702606798027,
	 * 0.04707731907072125, -0.007166494971835281, 2.0635704753653896,
	 * 0.9999999999998826, };
	 */

	public static double[] weight = { 28.226266218486995, 37.000776626069054,
			0.9840311302331121, 28.10746257995265, -20.819579797540918,
			1.6148248269093421, 15.346551161371503, 16.92099613291592,
			-0.1524653696426312, 13.635791064438022, 18.53748821795403,
			12.617460290004892, 2.3716157806351568, 42.52096485802233,
			7.65187092875129, 10.602110279163579, 15.38457719799342,
			6.593863401798697, };

	public static int test(List<List<List<double[]>>> data,
			List<List<List<Long>>> dict) {
		int acc = 0, all = 0;
		Iterator<List<List<double[]>>> contextIter = data.iterator();
		Iterator<List<List<Long>>> cUserIter = dict.iterator();
		while (contextIter.hasNext() && cUserIter.hasNext()) {
			List<List<double[]>> context = contextIter.next();
			all += context.size();
			acc += pageRank(context, cUserIter.next());
		}
		// System.out.println(acc + "/" + all + " = " + ((double)acc / all));
		return acc;
	}

	private static int pageRank(List<List<double[]>> context,
			List<List<Long>> cUser) {

		if (context == null || context.size() == 0) {
			System.out.println("Illegal input for pageRank()!");
			return 0;
		}

		// calculate the dimension and initialize jump vector
		int dim = 0; // the dimension of the matrix
		int[] start = new int[context.size() + 1]; // the start position of each
													// query
		start[0] = 0;
		int q = 1;
		List<Double> jumpList = new ArrayList<Double>();
		List<Long> idlist = new ArrayList<Long>();
		Iterator<List<double[]>> queryIter = context.iterator();
		Iterator<List<Long>> qUserIter = cUser.iterator();
		while (queryIter.hasNext() && qUserIter.hasNext()) {
			List<double[]> query = queryIter.next();
			List<Long> qUser = qUserIter.next();
			dim += query.size();
			start[q] = start[q - 1] + query.size();
			q++;
			Iterator<double[]> featureIter = query.iterator();
			Iterator<Long> userIter = qUser.iterator();
			while (featureIter.hasNext() && userIter.hasNext()) {
				Double score = MyMath.product(weight, featureIter.next());
				if (score < 0) {
					// System.out.println("Warning! Negative value");
					score = 0.0;
				}
				jumpList.add(score);
				idlist.add(userIter.next());
			}
			if (featureIter.hasNext() || userIter.hasNext()) {
				System.out
						.println("Fatal Error! feature list and user list do not match!");
			}
		}

		// System.out.println("dim = " + dim);
		// System.out.println("jumpList.size() = " + jumpList.size());
		// System.out.println("idlist.dize() = " + idlist.size());

		if (queryIter.hasNext() || qUserIter.hasNext()) {
			System.out.println("Fatal Error! data and dict do not match");
		}

		if (jumpList.size() != dim) {
			System.out.println("Fatal Error! Dimension unmatch!");
		}

		Double[] jump = new Double[jumpList.size()];
		jumpList.toArray(jump);
		Long[] id = new Long[idlist.size()];
		idlist.toArray(id);

		// initialize the relation matrix
		double[][] matrix = new double[dim][];
		for (int i = 0; i < dim; i++) {
			matrix[i] = new double[dim];
		}
		for (int i = 0; i < dim; i++) {
			for (int j = i + 1; j < dim; j++) {
				double relation = AccountRelationPool.evaluate(id[i], id[j]);
				matrix[i][j] = relation;
				matrix[j][i] = relation;
			}
		}

		// normalize relation matrix and jump vector
		// matrix = normalizeByRow(matrix);
		normalizeByRow(matrix);
		double[] djump = new double[jump.length];
		for (int i = 0; i < dim; i++) {
			djump[i] = jump[i];
		}
		// djump = normalizeSegment(djump, start);
		normalizeSegment(djump, start);
		double[] result = PageRank.getPageRank(matrix, djump, PageRank.alpha);

		int acc = 0;
		for (int i = 1; i < start.length; i++) {
			double target = result[start[i - 1]];
			boolean isRight = true;
			for (int j = start[i - 1] + 1; j < start[i]; j++) {
				if (target <= result[j]) {
					isRight = false;
					break;
				}
			}
			if (isRight) {
				acc++;
			}
		}

		// System.out.println("correct : " + acc + "/" + context.size());

		return acc;
	}

	public static double[][] normalizeByRow(double[][] matrix) {
		for (int i = 0; i < matrix.length; i++) {
			double sum = 0.0;
			for (int j = 0; j < matrix.length; j++) {
				sum += matrix[i][j];
			}
			if (sum == 0.0) {
				// System.out.println("Error! Unexpected sum of zero when normalize matrix!");
				double unit = 1.0 / (double) matrix.length;
				for (int j = 0; j < matrix.length; j++) {
					matrix[i][j] = unit;
				}
			} else {
				for (int j = 0; j < matrix.length; j++) {
					matrix[i][j] /= sum;
				}
			}
		}
		return matrix;
	}
	
	public static double[][] normalizeByRow(double[][] matrix, int[] start) {
		for (int i = 0; i < matrix.length; i++) {
			matrix[i] = PageRank.normalizeSegment(matrix[i], start);
		}
		return matrix;
	}

	public static boolean checkMatrixNormalized(double[][] matrix) {
		for (int i = 0; i < matrix.length; i++) {
			double sum = 0.0;
			for (int j = 0; j < matrix[i].length; j++) {
				sum += matrix[i][j];
			}
			if (Math.abs(sum - 1.0) > PageRank.epsilon) {
				return false;
			}
		}

		return true;
	}
	
	public static double[] normalizeVector(double[] v) {
		double sum = 0.0;
		for (int i = 0; i < v.length; i++) {
			sum += v[i];
		}
		if (sum == 0.0) {
			for (int i = 0; i < v.length; i++) {
				v[i] = (double)1.0 / v.length;
			}
		}
		else {
			for (int i = 0; i < v.length; i++) {
				v[i] /= sum;
			}
		}
		return v;
	}

	public static double[] normalizeSegment(double[] v, int[] start) {

		assert (start[start.length - 1] == v.length);

		if (start[start.length - 1] != v.length) {
			// System.out.println("Fatal Error! Wrong dimension when normalize vector!");
			return null;
		}

		double factor = 1.0 / (double) (start.length - 1);
		for (int i = 1; i < start.length; i++) {
			double sum = 0.0;
			for (int j = start[i - 1]; j < start[i]; j++) {
				sum += v[j];
			}
			if (sum == 0.0) {
				// System.out.println("Error! Unexpected sum of zero when normalize vector!");
				double unit = 1.0 / (double) (start[i] - start[i - 1]);
				unit *= factor;
				for (int j = start[i - 1]; j < start[i]; j++) {
					v[j] = unit;
				}
			} else {
				for (int j = start[i - 1]; j < start[i]; j++) {
					v[j] /= sum;
					v[j] *= factor;
				}
			}
		}
		return v;
	}

	public static boolean checkVectorNormalized(double[] v) {
		double sum = 0.0;
		for (int i = 0; i < v.length; i++) {
			if (v[i] < 0) return false;
			sum += v[i];
		}
		return Math.abs(sum - 1.0) < PageRank.epsilon;
	}

	private static double[] getPageRank(double[][] matrix, double[] jump,
			double alpha) {

		if (jump == null) {
			jump = new double[matrix.length];
			Arrays.fill(jump, (double) 1 / jump.length);
		}

		// check dimension
		if (matrix.length != jump.length) {
			System.out.println("Fatal Error! Matrix and vector do not match!");
			return jump;
		}

		// construct a new matrix of P = alpha * P' + (1 - alpha) * E
		// where E = e * transposition(v)
		double[][] data = new double[matrix.length][];
		for (int i = 0; i < matrix.length; i++) {
			data[i] = new double[jump.length];
		}

		double reAlpha = 1.0 - alpha;

		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < jump.length; j++) {
				data[i][j] = alpha * matrix[i][j] + reAlpha * jump[j];
			}
		}

		if (!checkMatrixNormalized(matrix)) {
			System.out.println("check matrix normalized failed");
			assert (checkMatrixNormalized(matrix));
		}
		if (!checkVectorNormalized(jump)) {
			System.out.println("check vector normalized failed");
			assert (checkVectorNormalized(jump));
		}

		return MyMath.eigenvector(data, jump, epsilon);
	}

	
	public static double gama = 0.1;
	public static double[] getFeatureVector(double[][] feature, double[] weight) {

		assert (feature[0].length == weight.length);

		double[] f = new double[feature.length];
		for (int i = 0; i < f.length; i++) {
			f[i] = Math.exp(MyMath.product(feature[i], weight) * gama);
//			f[i] = MyMath.product(feature[i], weight);
			assert (f[i] >= 0);
		}
		return f;
	}

	public static double[] predict(double[][] matrix, int[] start,
			double[][] feature, double[] w, double a) {
		assert (matrix.length == feature.length);
		double[] f = PageRank.getFeatureVector(feature, w);
//		System.out.println("Before normalization:");
//		MyMath.printVector(f);
		f = PageRank.normalizeSegment(f, start);
//		System.out.println("After normalization:");
//		MyMath.printVector(f);
		assert (PageRank.checkVectorNormalized(f));
		double[] p = PageRank.getPageRank(matrix, f, a);
		assert (PageRank.checkVectorNormalized(p));
		return p;
	}

	public static int test(double[][] matrix, int[] start, double[][] feature,
			double[] w, double a, int contextId) {
		double[] p = PageRank.predict(matrix, start, feature, w, a);
		int acc = 0;
		for (int i = 0; i < start.length - 1; i++) {
			boolean isAcc = true;
			double max = 0.0;
			int maxPos = 0;
			for (int j = start[i] + 1; j < start[i + 1]; j++) {
				if (p[j] >= p[start[i]]) {
					isAcc = false;
//					break;
				}
				if (p[j] > max) {
					max = p[j];
					maxPos = j;
				}
			}
			if (isAcc) {
				acc++;
			} else {
//				System.out.println("expected potential size = " + (start[i + 1] - start[i]));
				LinkerDriver.recordError(contextId, i, maxPos - start[i], start[i + 1] - start[i], "SRWError.txt");
			}
		}

		return acc;
	}

	public static double test(List<double[][]> relation,
			List<double[][]> feature, List<int[]> ruler, double[] w, double a) {
//		System.out.println("Context number: " + relation.size());

		int correct = 0;
		int all = 0;
		Iterator<double[][]> mIter = relation.iterator();
		Iterator<int[]> sIter = ruler.iterator();
		Iterator<double[][]> fIter = feature.iterator();
		int contextId = 0;
		while (mIter.hasNext() && sIter.hasNext() && fIter.hasNext()) {
			double[][] matrix = mIter.next();
			int[] start = sIter.next();
			double[][] f = fIter.next();
			correct += PageRank.test(matrix, start, f, w, a, contextId);

			all += start.length - 1;
			contextId++;
		}
		return (double) correct / all;
	}

}
